LeetCode——Z字形变换

NO.6 Z字形变换中等

思路一：按列写，按行读 将原字符串按列写成”Z字形”，写好之后按行读取“Z字形”。1.先创建一个有min(numRows,len(s))个元素的list，且list的每个元素都是一个StringBuilder。2.用两个变量分别记录当前是第几行和当前的方向。3.然后将参数字符串中的字符逐一填入。4.仅当前行等于list的第一个参数下标0或者等于numRows-1时方向改变。

这个思路很类似我们动手在纸上将参数字符串写成Z字形的过程，将所有字符逐一写出，在第一行写字符之后写字符的方向变为向下写，在最后一行（numRows）写字符之后写字符的方向变为向上写。当全部写完之后，按行将字符串读出：

public String convert(String s, int numRows) {
        if (numRows==1)return s;
        List<StringBuilder> list=new ArrayList<>();

        for (int i=0;i<Math.min(numRows,s.length());i++){
            list.add(new StringBuilder());
        }
//        定义一个变量记录方向，向下为false，向上为true
        boolean goingDown=false;
//        记录当前是第几行
        int currentRow=0;
        for (char c : s.toCharArray()) {
            list.get(currentRow).append(c);
//            如果当前行下标是第一行或者是最后一行，就改变方向标识
            if (currentRow==0||currentRow==numRows-1)goingDown=!goingDown;
//            行下标向当前方向移动，如果true就+1向下移动，如果是false就-1向上移动
            currentRow+=goingDown?1:-1;
        }

//        按行读取，获取最后的输出结果
        StringBuilder ret=new StringBuilder();
        for (StringBuilder stringBuilder : list) {
            ret.append(stringBuilder);
        }
        return ret.toString();
    }

时间复杂度：O(n)

思路二：直接按行访问 直接按照将参数字符串写成Z字形之后的结构进行按行访问拼接到结果字符串中。经过观察，可以发现如下规律：对于所有的行i和结果字符串中的字符索引k都有，1. 行0中的字符位于原字符串的k(2*numRows-2)索引处。 2. 行numRows-1中的字符位于原字符串的k(2*numRows-2)+numRows-1索引处。3. 内部的行i中的字符位于原字符串的k(2*numRows-1)+i以及(k+1)(2*numRows-2)-i索引处。

public String convert(String s, int numRows) {
    if (numRows==1)return s;
    int len=s.length();
    StringBuilder ans=new StringBuilder();
//        一个循环长度（Z字形两次方向变换，即向下写到numRows行方向变化为向上再写到0行的长度）
    int cycleLen=2*numRows-2;
//        0-numRows行
    for (int i=0;i<numRows;i++){
        for (int j=0;j+i<len;j+=cycleLen){
            ans.append(s.charAt(j+i));
//     当不是第0行且不是第numRows-1行且当前行下一个字符在原字符串中存在时，将当前行下一个字符加入结果串
//                防止遗漏中间行的字符
            if (i!=0&&i!=numRows-1&&j+cycleLen-i<len)
                ans.append(s.charAt(j+cycleLen-i));
        }
    }
    return ans.toString();
}

时间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.6 Z字形变换 中等

NO.6 Z字形变换中等